The present invention is generally related to logic circuits, and in particular to logic for implementing a linked list mechanism.
A linked list is a data structure used in application programs to store data that is dynamic in nature. A linked list comprises two basic components: a data element and a pointer to the next element in the linked list. In software, a linked list can grow simply by allocating memory from the operating system (OS) for each new node (entry) in the linked list. Conversely, a linked list can shrink by freeing the memory allocated for one or more nodes (entries) and returning it to the OS. The OS typically provides a memory management component to manage the allocation and deallocation of memory for a application.
In more specialized systems, memory resources are usually more limited and therefore must be allocated more efficiently. For example, there may not be sufficient memory capacity to provide for a sophisticated OS. Nonetheless, link list capability may still be needed for applications running on these specialized systems. One approach is for the application to allocate a block of memory and to manage the link lists from that memory. When more than one link list is needed, there are two approaches for allocating the link lists: statically or dynamically. Statically allocating memory for N linked lists is not an efficient allocation strategy. Some lists may grow beyond their statically allocated size, while other lists may be underutilized. Since the lists are statically allocated, memory from the underutilized lists cannot be allocated to lists which have grown beyond their predefined sizes. Dynamic allocation from the block of memory requires more processing time; however, memory usage is more efficient.